/*
题目链接 : https://leetcode.cn/problems/palindrome-partitioning-iv/
*/

//题解代码:
class Solution {
public:
    //Manacher算法
    void Manacher(string& s,vector<int>& len){
        int n = s.size();
        for(int i=0,c=0,r=0;i<n;++i){
            len[i] = i<r ? min(r-i,len[2*c-i]) : 0;
            while(i+len[i]<n && i-len[i]>=0 && s[i+len[i]]==s[i-len[i]]){
                ++len[i];
            }
            if(i+len[i]>r){
                r = i+len[i];
                c = i;
            }
        }
    }

    bool checkPartitioning(string s) {
        string t;
        for(auto& c : s){
            t += "#";
            t += c;
        }
        t += "#";

        int n = t.size();
        vector<int> len(n);
        Manacher(t,len);

        //枚举中间回文串的左右端点,注意枚举长度需要>=2,这是因为对原串s加了'#'
        for(int i=2;i<n;++i){
            for(int j=i+1;j<n-2;++j){
                int lmid = (i-1)/2,rmid = (j+1+n-1)/2,mid = (i+j)/2;
                if(2*len[mid]-1>=(j-i+1) && 2*len[lmid]-1>=i && 2*len[rmid]-1>=(n-j-1)) return true;
            }
        }
        return false;
    }
};
